package com.banmoon.algorithm.order;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 基数排序
 */
public class Demo07 {

    public static void main(String[] args) {
//        int[] arr = {128, 359, 26, 78, 98, 5, 789, 12, 6, 2};
        int[] arr = {2, 9, 7, 8, 3, 5, 4, 1, 6, 0};
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    public static int[] sort(int[] arr){
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(max<arr[i])
                max = arr[i];
        }
        int maxLength = String.valueOf(max).length();
        Map<Integer, LinkedList> containerMap = IntStream.range(0, 10).boxed()
                .collect(Collectors.toMap(Function.identity(), a -> new LinkedList()));
        for (int i = 0, n=1; i < maxLength; i++, n*=10) {
            for (int j = 0; j < arr.length; j++) {
                int temp = arr[j]/n%10;
                containerMap.get(temp).add(arr[j]);
            }
            final int[] index = {0};
            IntStream.range(0, 10).boxed().forEach(key -> {
                LinkedList list = containerMap.get(key);
                for (int k = 0; k < list.size(); k++) {
                    arr[index[0]] = (int) list.get(k);
                    index[0]++;
                }
                containerMap.put(key, new LinkedList());
            });
        }
        return arr;
    }

}
